package com.codingvip.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author hansongtao
 */
public class WallsAndGates {


    public static void main(String[] args) {
        int[][] rooms = WallsAndGates.init();
        WallsAndGates wallsAndGates = new WallsAndGates();
        wallsAndGates.wallsAndGates(new int[][]{});
        for (int i =0;i< rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                System.out.print(rooms[i][j]+" " );
            }
            System.out.println("");

        }
    }

    /**
     * INF  -1  0  INF
     * INF INF INF  -1
     * INF  -1 INF  -1
     *   0  -1 INF INF
     */
    public static int[][] init() {
        int[][] rooms = new int[][]{
                new int[]{EMPTY, WALL, GATE, EMPTY},
                new int[]{EMPTY, EMPTY, EMPTY, WALL},
                new int[]{EMPTY, WALL, EMPTY, WALL},
                new int[]{GATE, WALL, EMPTY, EMPTY},
        };
        return rooms;
    }

    private static final int EMPTY = Integer.MAX_VALUE;
    private static final int GATE = 0;
    private static final int WALL= -1;
    private static final List<int[]> DIRECTIONS = Arrays.asList(
            new int[]{1, 0}, //下
            new int[]{-1, 0},//上
            new int[]{0, 1},//右
            new int[]{0, -1}//左
    );
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        int totalRows = rooms.length;

        int totalColumns = rooms[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < totalRows; i++) {
            for (int j = 0; j < totalColumns; j++) {
                if (rooms[i][j] == GATE) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            for (int[] ints : DIRECTIONS) {
                int r = row + ints[0];
                int c = col + ints[1];
                if (r < 0 || c < 0 || r >= totalRows || c >= totalColumns || rooms[r][c] == WALL
                    || rooms[r][c]==GATE) {
                    continue;
                }
                if (rooms[r][c] != EMPTY) {
                    continue;
                }
                rooms[r][c] = rooms[row][col] + 1;
                queue.add(new int[]{r, c});
                System.out.println("Current:"+r+","+c+";==>Queue size;"+queue.size());
            }

        }


    }

}
